package by2019;

import java.util.HashMap;
import java.util.Map;

/*
 * 给定一个整数数组和一个目标值，找出数组中和为目标值的两个值
 * 并且返回他们的下标
 */

public class 两数之和 {
	
	public static void main(String[] args) {
		int[] nums = new int[] {3,2,4};
		int[] an = twoSumPro(nums, 6);
		for(int i : an) {
			System.out.print(i+" ");
		}
	}
	
	//LeetCode官方解答，但是我觉得有问题
	private static int[] twoSum(int[] nums, int target) {
		
		Map<Integer, Integer> map = new HashMap<Integer, Integer>() ;
		
		 for (int i = 0; i < nums.length; i++) {
		        int complement = target - nums[i];
		        if (map.containsKey(complement)) {
		            return new int[] { map.get(complement), i };
		        }
		        map.put(nums[i], i);
		    }
		 throw new IllegalArgumentException("No two sum solution");
    }
	
	
	//暴力破解，时间复杂度为O(N^2)
	private static int[] twoSumX(int[] nums, int target) {
		for(int i=0; i<nums.length; i++) {
			for(int j=i; j<nums.length; j++) {
				if(nums[i]+nums[j]==target)
					return new int[] {i, j};
			}
		}
		throw new IllegalArgumentException("No two sum solution");
	}
	
	//利用map查找，用空间换取速度，map查找的时间复杂度为O(1),用map查找抵消了一层遍历
	public static int[] twoSumPro(int[] nums, int target) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for(int i=0;i<nums.length;i++) {
			 map.put(nums[i], i);
		}
		System.out.println("map注入完成");
		for(int i=0;i<nums.length;i++) {
			if(map.containsKey(target-nums[i]) ) {
				if(i==map.get(target-nums[i]))
					continue ;
				return new int[] {i, map.get(target-nums[i])};
			}
		}
		return nums ;
	}

}
